package 左哥算法.ch20树状数组;

/**
 * 推荐查看：{@link 题目集.线段树or树状数组.树状数组.ch01_模板}
 */
public class TreeArray {
    private int[] tree;
    private int[] arr;
    public TreeArray(int[] origin) {
        this.tree =new int[origin.length+1];
        this.arr =new int[origin.length+1];
        for (int i = 0; i < origin.length; i++) {
//            arr[i+1]=origin[i];
            add(i+1,origin[i]);
        }
        System.arraycopy(origin,0,arr,1,origin.length);
    }
    public void add(int i,int val){
        arr[i]+=val;
        while (i<tree.length){
            tree[i]+=val;
            i+=lowbit(i);
        }
    }
    public void update(int i,int val){
        add(i,val-arr[i]);  //做差相加
        arr[i]=val;
    }

    /**
     * 取x的最后一位1
     */
    private int lowbit(int x){
        return x&-x;    //等价于 x&(~x+1)
    }
    public int sumRange(int l,int r){
        return query(r)-query(l-1);
    }
    public int query(int i){
        int ans=0;
        while (i>0){
            ans+=tree[i];
            i-=lowbit(i);   //向上提一层
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr={1, 3, 5};
        TreeArray treeArray = new TreeArray(arr);
        System.out.println(treeArray.sumRange(1,3));
        treeArray.update(2,2);
        System.out.println(treeArray.query(3));
    }
}
